package Sort;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2022-04-18 11:20
 */
public class Up2DownMergeSort<T extends Comparable<T>> extends Sort<T> {
    protected T[] temp;
    protected void merge(T[] nums,int l,int r){
        int mid=l+(r-l)/2;
        int i=l,j=mid+1;
        for (int k = l; k<=r ; k++) {
            temp[k]=nums[k];
        }
        for (int k = l; k <=r ; k++) {
            if (i>mid){
                //前半部分已经合并完成
                nums[k]=temp[j++];
            }else if (j>r){
                nums[k]=temp[i++];
            }else if (temp[i].compareTo(temp[j])<=0){
                nums[k]=temp[i++];//先将前半部小的时候合并，保证稳定性
            }else {
                nums[k]=temp[j++];
            }
        }
    }
    private void sort(T[] nums,int l,int r){
        if (r<=l){
            return;
        }
        int mid=l+(r-l)/2;
        sort(nums,l,mid);
        sort(nums,mid+1,r);
        merge(nums,l,r);
    }

    @Override
    public void sort(T[] nums) {
        temp= (T[]) new Comparable[nums.length];
        sort(nums,0,nums.length-1);
    }
    public static void main(String[] args) {
        Integer[] nums={3,5,6,4,1,2};
        Up2DownMergeSort<Integer> up2DownMergeSort=new Up2DownMergeSort<Integer>();
        up2DownMergeSort.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
